今天的題單：

• Ransom Note

• Climbing Stairs

383. Ransom Note

判斷 magazine 字串內的字母能不能拼出 ransomNote 字串。

思路：個別紀錄 magazine 和 ransomNote 中每個字母的出現次數，再看 ransomNote 的字母在 magazine 中足不足夠。

實作一：用 map

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        // map (sorted)
        map<char, int> map_R;
        map<char, int> map_M;

        for (int i = 0; i < ransomNote.length(); i++) {
            if (map_R.find(ransomNote[i]) == map_R.end()) {
                map_R[ransomNote[i]] = 1;
            } else {
                map_R[ransomNote[i]]++;
            }
        }

        for (int i = 0; i < magazine.length(); i++) {
            if (map_M.find(magazine[i]) == map_M.end()) {
                map_M[magazine[i]] = 1;
            } else {
                map_M[magazine[i]]++;
            }
        }
        
        map<char, int>::iterator it_R;

        for (it_R = map_R.begin(); it_R != map_R.end(); it_R++) {
            if (map_M.find(it_R->first) == map_M.end()) { // not found
                return false;
            }

            if (map_R[it_R->first] > map_M[it_R->first]) { // not enough
                return false;
            }
        }
        return true;
    }
};

實作二：題目說字母只有 lowercase letter，可以用改用固定長度 array 紀錄字母次數

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        // array
        vector<int> vec_R(26, 0);
        vector<int> vec_M(26, 0);

        for (int i = 0; i < ransomNote.length(); i++) {
            vec_R[ransomNote[i] % 26]++;
        }

        for (int i = 0; i < magazine.length(); i++) {
            vec_M[magazine[i] % 26]++;
        }

        for (int i = 0; i < vec_R.size(); i++) {
            if (vec_M[i] < vec_R[i])
                return false;
        }
        return true;

    }
};

優化：可以只紀錄 magazine 的字母個數，之後 loop ransomNote 時減去相應字母的數量，如果不夠減，或是字母沒出出現，就表示不夠組成。

• 可以省去 ransomNote 的字母數量表和一個 loop

• 也可以使用 Unordered_map (Leetcode sample code)，查找也是 O(1)。不過以這題的限制，用 array 應該最簡單。

// Leetcode sample code
class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
       unordered_map<char, int> charCount;

        for(char c: magazine){
            charCount[c]++;
        }
        for(char c: ransomNote){
            if(charCount[c] == 0){
                return false;
            }
            charCount[c]--;
        }
        return true;
    }
};

70. Climbing Stairs

經典爬樓梯題。一次只能爬一格或兩格，計算爬到第 n 層有幾種爬法。

這題可以觀察一下前幾層的爬法：爬到第 n 層需要 T(n) 種爬法

• 第一層：只有 1 一種走法 → T(1) = 1

• 第二層：可以走 1+1 或 2 → T(2) = 2

• 第三層：可以從第一層走 2 步或從第二層走 1 步 → T(3) = T(1) + T(2) = 3

之後以此類推，得到一個遞迴式：T(n) = T(n-1) + T(n-2)，正是 fibonacci 數列。

實作一：使用 recursion，結果 TLE

class Solution {
public:
    int climbStairs(int n) {
        // fibonacci
        return fib(n);
    }

    int fib(int n) {
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }

        return fib(n-1) + fib(n-2);
    }
};

實作二：改成 iterative 作法

class Solution {
public:
    int climbStairs(int n) {
        vector<int> fib(60, 0);
        
        fib[0] = 1;
        fib[1] = 1;
        fib[2] = 2;

        for (int i = 3; i <= n; i++) {
            fib[i] = fib[i-1] + fib[i-2];
        }
        return fib[n];
    }
};